class Solution {
public:
    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fduplicate-zeros%2F
    void duplicateZeros1(vector<int>& arr) 
    {
        vector<int> arr1;//额外创建一个数组是不合适的
        int num = arr.size();
        int i = 0;
        for( ; i < num; i++)
        {
            if(arr[i] == 0)
            {
                arr1.push_back(0);
                num--;
            }
            arr1.push_back(arr[i]);
        }
        if(i != num)
        {
            arr1.pop_back();//倘若arr中全部为0，num--且i++故会多出一个元素
        }

        arr = arr1;
    }

    void duplicateZeros(vector<int>& arr) //双指针解法，先根据“异地”操作，然后再优化成双指针的就地操作
    {
        int cur = 0,dest = -1;
        int n = arr.size();
        while(cur < n)
        {
            if(arr[cur] == 0) dest++;
            dest++;
            if(dest >= n -1) break;//该题目主要还是对边界的控制
            //画图便可发现当dest以经到最后一个位置时，cur便不需要在++
            cur++;
        }
        if(dest == n)//最后一个cur可能导致dest越界，也可能不会故判断dest而不是arr[cur] == 0
        {        
            dest--;
            arr[dest--] = 0;
            cur--;
        }
        while(dest >= 0)
        {
            if(arr[cur] == 0) arr[dest--] = 0;
            arr[dest--] = arr[cur--];
        }
    }


    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fhappy-number%2F
    int bitsum(int sum)
    {
        int cnum = 0;
        while(sum != 0)
        {
            int num = sum%10;
            cnum += num*num;
            sum /= 10;
        }
        return cnum;
    }
    bool isHappy(int n) 
    {
        int fast = bitsum(n), slow = n;//快慢指针倘若成环fast则会追上slow
        while(slow != fast)
        {
            slow = bitsum(slow);
            fast = bitsum(bitsum(fast));
            if(fast == 1) return true;
        }
        return slow == 1;//还有n= 1的情况
    }

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fcontainer-with-most-water%2F
    int maxArea(vector<int>& height) 
    {
        int v = 0;
        int left = 0, right = height.size() - 1;
        while(left < right)
        {
            long v1 = 0;
            if(height[left] > height[right])//采用双指针思想是让高度矮的指针移位置时间O(n)
            {
                v1 = (right - left) * height[right];
                right--;
            }
            else
            {
                v1 = (right - left) * height[left];
                left++;
            }
            if(v1 > v)
            {
                v = v1;
            }
        }
        return v;
    }
};